package com.cango.student.algorithm.nodepackage;

import com.cango.student.algorithm.NodeSort;

public class MergeSortLink {

    /**
     * 两个有序列表合并
     * @param node1
     * @param node2
     * @return
     */
    public static Node mergeSortLink(Node node1, Node node2) {
        Node newHead = new Node();
        // 必须
        Node localNode = newHead;
        while(node1 != null && node2 != null) {
            if (node1.data < node2.data) {
                localNode.next = node1;
                node1 = node1.next;
            } else {
                localNode.next = node2;
                node2 = node2.next;
            }

            localNode = localNode.next;
        }

        if (node1 != null) {
            localNode.next = node1;
        }
        if (node2 != null) {
            localNode.next = node2;
        }
        return newHead.next;
    }

    /**
     * 两个有序列表合并
     */
    public static void main(String[] args) {
        Node linkNode1 = new Node();
        linkNode1.data = 1;
        Node linkNode2 = new Node();
        linkNode2.data = 3;
        Node linkNode3 = new Node();
        linkNode3.data = 5;
        Node linkNode4 = new Node();
        linkNode4.data = 7;
        Node linkNode5 = new Node();
        linkNode5.data = 9;

        linkNode1.next = linkNode2;
        linkNode2.next = linkNode3;
        linkNode3.next = linkNode4;
        linkNode4.next = linkNode5;

        Node linkNodeA = new Node();
        linkNodeA.data = 2;
        Node linkNodeB = new Node();
        linkNodeB.data = 4;
        Node linkNodeC = new Node();
        linkNodeC.data = 6;
        Node linkNodeD = new Node();
        linkNodeD.data = 8;
        Node linkNodeE = new Node();
        linkNodeE.data = 10;
        Node linkNodeF = new Node();
        linkNodeF.data = 11;
        Node linkNodeG = new Node();
        linkNodeG.data = 12;

        linkNodeA.next = linkNodeB;
        linkNodeB.next = linkNodeC;
        linkNodeC.next = linkNodeD;
        linkNodeD.next = linkNodeE;
        linkNodeE.next = linkNodeF;
        linkNodeF.next = linkNodeG;

        Node node = mergeSortLink(linkNode1, linkNodeA);
        while (node != null) {
            System.out.println(node.data);
            node = node.next;
        }

    }
}
